#include <dbg.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);  // 邻接表
        for (const auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);  // 有向边
        }
        dbg(graph);

        vector<int> colors(numCourses, 0);  // 0 未访问，1 正在访问，2 已访问
        for (int i = 0; i < numCourses; ++i) {
            if (colors[i] == 0 && dfs(graph, colors, i)) {
                return false;  // 有环
            }
        }
        return true;  // 无环
    }

private:
    bool dfs(vector<vector<int>>& graph, vector<int>& colors, int x) {
        colors[x] = 1;  // 标记为正在访问
        for (int y : graph[x]) {
            if (colors[y] == 1 || /* 有环 */
                (colors[y] == 0 &&
                 dfs(graph, colors, y) /* 还未访问，继续搜索 */)) {
                return true;  // 有环
            }
        }
        colors[x] = 2;  // 标记为已访问
        return false;   // 无环
    }
};

TEST(TEST1, canFinish) {
    Solution s;

    vector<vector<int>> prerequisites{
        {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}, {1, 3}};
    EXPECT_EQ(s.canFinish(5, prerequisites), false);
}

TEST(TEST2, canFinish) {
    Solution s;

    vector<vector<int>> prerequisites{{1, 0}};
    EXPECT_EQ(s.canFinish(2, prerequisites), true);
}

int main(int argc, char* argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}